package sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class CountingSort {

    public static void countingSort(int[] arr) {
        if(arr == null || arr.length <= 1){
            return;
        }

        int max = getMaxValue(arr);
        countingSort(arr, max);
    }

    private static void countingSort(int[] arr, int max){
        int bucketLen = max + 1;
        int[] bucket = new int[bucketLen];

        for(int value : arr){
            bucket[value]++;
        }
        int sortedIndex = 0;
        for(int j = 0; j<bucketLen; j++){
            while (bucket[j] > 0){
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
    }

    private static int getMaxValue(int[] arr){
        int max = arr[0];
        for(int value : arr){
            if(value > max){
                max = value;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
        countingSort(arr);
        System.out.println(Arrays.stream(arr).boxed().collect(Collectors.toList()));
    }


}
